Day 17: LeetCode 1143. Longest Common Subsequence

Source

https://leetcode.com/problems/longest-common-subsequence/

1.題意:

經典題: 找最長的共同子序列。

2.思路:

• 待圖解

3.程式碼:

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len1 = len(text1) # abcde(5) -- row
        len2 = len(text2) # ace(3) -- col
        
        R = [[0 for _ in range(len2+1)] for _ in range(len1+1)]
        #print(R)
        '''
        for i in range(len1+1):
            for j in range(len2+1):
                print(R[i][j],end="")
            print()
        '''    
        # len1: row
        # len2: col
        
        for i in range(len1+1):
            for j in range(len2+1):
                if i==0 or j==0:
                    R[i][j] = 0
                    
                elif text1[i-1]==text2[j-1]: #R-i:text-(i-1),R-j:text-(j-1) 
                    R[i][j] = R[i-1][j-1]+1  #左上位置的值+1
                else:
                    R[i][j] = max(R[i-1][j],R[i][j-1]) #上一row同一col vs 上一col同一row 取大
        #print(R)            
        return R[len1][len2]            
                    
                    
                    
                    
                    

Result

待優化

補充

R = [[0 for _ in range(col+1)] for _ in range(row+1)]
建立row+1個列 col+1個行

• 如何在 Python 中建立二維陣列

參考

1. https://leetcode.com/problems/longest-common-subsequence/discuss/436719/Python-very-detailed-solution-with-explanation-and-walkthrough-step-by-step
2. https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
   • https://www.youtube.com/watch?v=HgUOWB0StNE

Backup article

Day17 at HackMD